3693. Maximum Sum

You are given a sequence a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁸, 2 ≤ n ≤ 10⁵). There are two types of operations and they are defined as follows:

Update:

This will be indicated in the input by a 'U' followed by space and then two integers i and x.

U i x, 1 ≤ i ≤ n и 0 ≤ x ≤ 10⁸

This operation sets the value of a_i to x.

Query:

This will be indicated in the input by a 'Q' followed by a single space and then two integers i and j.

Q x y, 1 ≤ x < y ≤ n

You must find i and j such that x ≤ i, j ≤ y and i ≠ j, such that the sum a_i + a_j is maximized. Print the sum a_i + a_j.

Input. The first line consists of an integer n representing the length of the sequence. Next line consists of n integers a_i. Next line contains an integer q (q ≤ 10⁵), representing the number of operations. Next q lines contain the operations.

Output. Print in a separate line the maximum sum mentioned above for each Query.

Sample input	Sample output
5 1 2 3 4 5 6 Q 2 4 Q 2 5 U 1 6 Q 1 5 U 1 7 Q 1 5	7 9 11 12

РЕШЕНИЕ

структуры данных – дерево отрезков

Анализ алгоритма

Выполнение запроса Query заключается в нахождении двух наибольших элементов a_i и a_j на отрезке [x; y] (x ≤ i, j ≤ y, i ≠ j). Используем дерево отрезков для поддержания первого и второго максимума на отрезках. Функция Update совершает модификацию одного элемента.

Реализация алгоритма

#include <cstdio>

#include <algorithm>

#define MAX 100010

using namespace std;

struct node

{

int max1, max2; // первый и второй максимумы

} SegTree[4*MAX];

int i, j, q, n, a[MAX];

int x, y;

char ch;

int max(int i, int j)

{

return (i > j) ? i : j;

}

void BuildTree(int *a, int Vertex, int Left, int Right)

{

if (Left == Right)

{

SegTree[Vertex].max1 = a[Left];

SegTree[Vertex].max2 = 0;

}

else

{

int Middle = (Left + Right) / 2;

BuildTree(a, 2*Vertex, Left, Middle);

BuildTree(a, 2*Vertex+1, Middle+1, Right);

int temp[] = {SegTree[2*Vertex].max1, SegTree[2*Vertex].max2,

SegTree[2*Vertex+1].max1, SegTree[2*Vertex+1].max2};

sort(temp,temp+4);

SegTree[Vertex].max1 = temp[3];

SegTree[Vertex].max2 = temp[2];

}

}

node Query(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right)

{

node n; n.max1 = n.max2 = 0;

return n;

}

if ((Left == LeftPos) && (Right == RightPos)) return SegTree[Vertex];

int Middle = (LeftPos + RightPos) / 2;

node L = Query(2*Vertex, LeftPos, Middle, Left, min(Right,Middle));

node R = Query(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1),

Right);

node Result;

int temp[] = {L.max1, L.max2, R.max1, R.max2};

sort(temp,temp+4);

Result.max1 = temp[3]; Result.max2 = temp[2];

return Result;

}

void update(int Vertex, int LeftPos, int RightPos,

int Position, int NewValue)

{

if (LeftPos == RightPos)

{

SegTree[Vertex].max1 = NewValue;

SegTree[Vertex].max2 = 0;

return;

}

else

{

int Middle = (LeftPos + RightPos) / 2;

if (Position <= Middle)

update (2*Vertex, LeftPos, Middle, Position, NewValue);

else update (2*Vertex+1, Middle+1, RightPos, Position, NewValue);

int temp[] = {SegTree[2*Vertex].max1, SegTree[2*Vertex].max2,

SegTree[2*Vertex+1].max1, SegTree[2*Vertex+1].max2};

sort(temp,temp+4);

SegTree[Vertex].max1 = temp[3];

SegTree[Vertex].max2 = temp[2];

}

}

int main(void)

{

scanf("%d",&n);

for(i = 0;i < n; i++) scanf("%d",&a[i]);

BuildTree(a,1,0,n-1);

scanf("%d",&q);

for(j = 0; j < q; j++)

{

scanf("\n%c ",&ch);

if(ch == 'Q')

{

scanf("%d %d",&x,&y);

node Res = Query(1,0,n-1,x-1,y-1);

printf("%d\n",Res.max1 + Res.max2);

} else

{

scanf("%d %d",&i,&x);

update(1, 0, n - 1, i - 1, x) ;

}

}

return 0;

}